package Graph.graphWithWeight;

import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/3 12:43
 * @Version 1.0
 *
 *
 *
 */

public class GraphWeight implements Cloneable {
    //节点数
    private int V;
    //边数
    private int E;
    //因为是 有权图，所有用TreeMap 是一个键值对 <顶点，权值>
    private TreeMap<Integer,Integer>[] adj;


    public GraphWeight(String filename){

        //从文件中读出  图的基本信息。
        File file = new File(filename);

        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) {
                throw new IllegalArgumentException("V must be non-negative");
            }
            //首先 先申请整个数组的 的内存空间。 申请V 个 LinkedList 空间 为后续的数组LinkedList做准备。
            adj = new TreeMap[V];
            for(int i = 0; i < V; i ++) {
                adj[i] = new TreeMap<Integer, Integer>();
            }

            E = scanner.nextInt();
            if(E < 0) {
                throw new IllegalArgumentException("E must be non-negative");
            }

            for(int i = 0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);
                int weight = scanner.nextInt();

                if(a == b) {
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                if(adj[a].containsKey(b)) {
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                }

                adj[a].put(b,weight);
                adj[b].put(a,weight);
            }
        }
        catch(IOException e){
            e.printStackTrace();
        }
    }

    public void validateVertex(int v){
        if(v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + "is invalid");
        }
    }

    @Override
    protected Object clone() {
        //默认的clone 是浅拷贝，我们需要深拷贝。 深拷贝其实就是把现在这个Graph 整个对象的详细细节（比如图的具体构造 邻接边什么的）也拷贝进去
        try {
            GraphWeight clone = (GraphWeight)super.clone();
            //做Graph 的深拷贝           -----开始
            clone.adj = new TreeMap[V];
            for(int v=0;v<V;v++){
                clone.adj[v] = new TreeMap<>();
                //① 这种方法 性能比较差
                /*for(int w:adj[v].keySet()){
                    clone.adj[v].put(w,adj[v].get(w));
                }*/
                //② 这种方法 性能比较好
                //adj[v].entrySet() 就是adj[v]下的一个一个键值对。 而Map.Entry<Integer,Integer>就是其中的一个键值对
                for(Map.Entry<Integer,Integer> entry:adj[v].entrySet()){
                    clone.adj[v].put(entry.getKey(),entry.getValue());
                }
            }
            //做Graph 的深拷贝           -----结束
            return clone;
        }catch (CloneNotSupportedException e){
            e.printStackTrace();
        }
        //如果有异常直接返回 null
        return null;
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public boolean hasEdge(int v, int w){
        validateVertex(v);
        validateVertex(w);
        return adj[v].containsKey(w);
    }

    public int getWeight(int v,int w){
        if(hasEdge(v,w)){
            return adj[v].get(w);
        }
        throw new IllegalArgumentException(String.format("No edge %d-%d",v,w));
    }

    public Iterable<Integer> adj(int v){
        validateVertex(v);
        //不能直接返回TreeMap ，因为TreeMap没有实现Iterable<Integer> 接口，而keySet()实现了，keySet()是TreeMap的key集合
        return adj[v].keySet();
    }

    public int degree(int v){
        return adj[v].size();
    }

    public void removeEdge(int v,int w){
        validateVertex(v);
        validateVertex(w);
        //因为是一个无向图，所以两边都要删除
        adj[v].remove(w);
        adj[w].remove(v);
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();

        sb.append(String.format("V = %d, E = %d\n", V, E));
        for(int v = 0; v < V; v ++){
            sb.append(String.format("%d : ", v));
            /*for(int w : adj[v]) {
                sb.append(String.format("%d ", w));
            }*/
            for(Map.Entry<Integer,Integer> entry:adj[v].entrySet()){
                sb.append(String.format("(%d,%d)",entry.getKey(),entry.getValue()));
            }
            sb.append('\n');
        }
        return sb.toString();
    }

    public static void main(String[] args){

        GraphWeight adjSet = new GraphWeight("gWeight.txt");
        System.out.print(adjSet);
    }


}
